Media content hosting sites implement mechanisms for identifying unauthorized videos. Media hosting services that allow users to upload multimedia content (e.g., audio/video content) for mass viewing provide easy distribution of global events regardless of demographic agenda. As volume of hosted media content continues to grow, management of ownership rights pertaining to hosted media content becomes an increasingly challenging problem for hosting services. For music content embedded in an audio or video file, for example, the songwriter, the publisher, and the recording label are just some of the many entities that may hold rights to the media content. For appropriate payments to be made to copyright holders, media content must be correctly identified. However, unlike television and radio environments where the content is typically identified prior to airing, media hosting services often handle user-provided media content that may initially be unidentified. Manual identification of such media content becomes onerous when media hosting sites receive thousands or millions of new media uploads every day, and traditional automated mechanisms lack robustness and scalability required for modern media hosting services.